This track of the course covers the topic "Queue".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Queue.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
Through this video, we will learn the Implementation of a queue using an array.
Codes:
Through this video, we will learn the Implementation of a queue using a LinkedList.
Codes:
This video discusses the implementation of Queue in C++ STL. We will also learn various operations that the Queue STL libraries have to provide.
Codes:
In this video we'll talk about Queue in Java
Codes:
This video discusses the implementation of the stack using a queue.
Codes:
This video discusses the efficient approach of Reversing a Queue.
Codes:
This video discusses the below problem:
Given a number n, print first n number(in increasing order) such that all these numbers have digits in set {5, 6}
Codes:
Array = queue[N].
front = 0, rear = N-1.
N = 5.
Operation 1:
enque(5);
front = 0,
rear = (N-1 + 1)%N = 0.
Queue contains: [5].
Operation 2:
enque(10);
front = 0,
rear = (rear + 1)%N = (0 + 1)%N = 1.
Queue contains: [5, 10].
Operation 3:
enque(15);
front = 0,
rear = (rear + 1)%N = (1 + 1)%N = 2.
Queue contains: [5, 10, 15].
Operation 4:
deque();
print queue[front];
front = (front + 1)%N = (0 + 1)%N = 1.
Queue contains: [10, 15].
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40
queue< data_type > queue_name;
where,
data_type is the type of element to be stored
in the queue.
queue_name is the name of the queue data structure.
The queue gquiz is : 10 20 30
gquiz.size() : 3
gquiz.front() : 10
gquiz.back() : 30
gquiz.pop() : 20 30
Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4
A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.


Why have we taken a pointer that points to the last node instead of first node?
For insertion of node in the beginning we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of start pointer we take a pointer to the last node then in both the cases there won’t be any need to traverse the whole list. So, insertion in the begging or at the end takes constant time irrespective of the length of the list.6 4 2 8 12 10

push(s, x) // x is the element to be pushed and s is stack
1) Enqueue x to q2
2) One by one dequeue everything from q1 and enqueue to q2.
3) Swap the names of q1 and q2
// Swapping of names is done to avoid one more
// movement of all elements from q2 to q1.
pop(s)
1) Dequeue an item from q1 and return it.
current size: 3
3
2
1
current size: 1
push(s, x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
1) One by one dequeue everything except the last element
from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item
is the result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more
// movement of all elements from q2 to q1.
current size: 4
4
3
2
current size: 2

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
Here the time complexity will be O(n)
deQueue(q)
1) If stack1 is empty then print an error
2) Pop an item from stack1 and return it
Here time complexity will be O(1)
1
2
3
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
Here time complexity will be O(n)
1 2 3
Input : Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]Solution - The idea is to use an auxiliary stack and follow these steps to solve the problem -
k = 5
Output : Q = [50, 40, 30, 20, 10, 60, 70, 80, 90, 100]
/* Function to reverse the first K elements of the Queue */Time Complexity : O(n) , n : size of queue
void reverseQueueFirstKElements(k, Queue)
{
if (Queue.empty() == true || k > Queue.size())
return
if (k <= 0)
return
stackStack
/* Push the first K elements into a Stack*/
for ( i = 1 to k) {
Stack.push(Queue.front())
Queue.pop()
}
/* Enqueue the contents of stack
at the back of the queue*/
while (!Stack.empty()) {
Queue.push(Stack.top())
Stack.pop()
}
/* Remove the remaining elements and
enqueue them at the end of the Queue*/
for (int i = 0 to i < Queue.size() - k) {
Queue.push(Queue.front())
Queue.pop()
}
}
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
void printKMax(arr[], n, k)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
deque < int > Qi(k)
/* Process first k (or first window) elements of array */
for (i = 0; i < k; ++i) {
// For every element, the previous smaller elements are useless so
// remove them from Qi
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back() // Remove from rear
// Add new element at rear of queue
Qi.push_back(i)
}
// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the largest element of
// previous window, so print it
print (arr[Qi.front()])
// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front() // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back()
// Add current element at the rear of Qi
Qi.push_back(i)
}
// Print the maximum element of last window
print (arr[Qi.front()])
}
Asked In: Goldman Sachs Amazon
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon
Asked In: Amazon FactSet Microsoft Morgan Stanley Zoho
A | When a resource is shared among multiple consumers. |
B | When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes |
C | Load Balancing |
D | All of the above |